package com.fwpsl.tree;

import java.util.*;

/**
 * @author: 风戏fw
 * @date: 2024/2/22
 * @description: 二叉树的遍历
 * 1. 递归方式：时间复杂度O(n)，空间复杂度O(n)。
 * 2. 迭代方式：先把所有左子树入栈，直到叶子节点，再依次出栈，每次出栈后遍历右子树。时间复杂度O(n)，空间复杂度O(n)。
 * 前序入栈时输出；中序出栈时输出；后序对父节点增加标识。
 * 3. Morris方式：把每个节点的前驱节点的右子树指向自己，分两种：前驱节点指向当前节点、清连接。
 * 如果当前节点没有前驱节点则直接输出（前序、中序）；有前驱节点时，前序指向时输出，中序清连接时输出，后序清连接时把左子节点到前驱节点倒序输出。
 * <p>
 * Morris(莫里斯)序就是把空间复杂度优化到O(1)的二叉树遍历算法。Morris遍历用到了“线索二叉树”的概念。
 * 利用叶子结点的右空指针来存储某种遍历的前驱结点。因此没有额外的使用的空间。
 */
public class TreeTraversal {

    /**
     * 前序遍历 - 递归
     */
    public static <T> void preorderTraversal(Tree.Node<T> root) {
        // 递归的结束条件。
        if (null == root) {
            return;
        }

        System.out.print(root.val + "\t");
        // 遍历左子树。
        preorderTraversal(root.left);
        // 遍历右子树
        preorderTraversal(root.right);
    }

    /**
     * 前序遍历 - 迭代
     */
    public static <T> void preorderTraversal2(Tree.Node<T> root) {
        // 前序遍历使用的栈。
        Deque<Tree.Node<T>> stack = new LinkedList<>();
        while (!stack.isEmpty() || null != root) {
            // 加入左节点.
            while (null != root) {
                // 因为是前序遍历将节点的值加入ans中。
                System.out.print(root.val + "\t");

                stack.push(root);
                root = root.left;
            }

            // 遍历右子树。
            root = stack.pop().right;
        }
    }

    /**
     * 前序遍历 - 迭代，简单逻辑
     */
    public static <T> void preorderTraversal2_2(Tree.Node<T> root) {
        if (null == root) {
            return;
        }

        Deque<Tree.Node<T>> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Tree.Node<T> node = stack.pop();
            if (null != node) {
                // 压入右节点。
                if (null != node.right) {
                    stack.push(node.right);
                }

                // 压入左节点。
                if (null != node.left) {
                    stack.push(node.left);
                }

                // 压入根节点。
                stack.push(node);
                // 压入一个null值，作为分隔符。
                stack.push(null);
            } else {
                // 当node=null的时候，将节点的值加入集合当中。
                System.out.print(stack.pop().val + "\t");
            }
        }
    }

    /**
     * 前序遍历 - Morris
     * <p>
     * 1. 当前节点没有前驱节点(左子节点为空)，直接将当前节点加入答案，并遍历当前节点的右子节点
     * 2. 当前节点有前驱节点(左子节点不为空)，找到当前节点的前驱节点：
     * 2.1 前驱节点的右子节点为空： 将当前节点加入答案，并将前驱节点的右子节点更新为当前节点。当前节点更新为当前节点的左子节点(开始遍历左子树)。
     * 2.2 前驱节点的右子节点为当前节点： 将它的右子节点重新设为空(结束遍历左子树)。当前节点更新为当前节点的右子节点(开始遍历右子树)。
     */
    public static <T> void preorderTraversal3(Tree.Node<T> root) {
        if (root == null) {
            return;
        }

        // p1为当前节点，p2为前驱节点
        Tree.Node<T> p1 = root, p2 = null;
        while (p1 != null) {
            p2 = p1.left;
            if (p2 != null) {
                // 两种情况： 找前驱节点、置空前驱节点的右子树
                while (p2.right != null && p2.right != p1) {
                    p2 = p2.right;
                }

                if (p2.right == null) {
                    System.out.print(p1.val + "\t");
                    p2.right = p1;
                    p1 = p1.left;
                } else {
                    p2.right = null;
                    p1 = p1.right;
                }
            } else {
                System.out.print(p1.val + "\t");
                p1 = p1.right;
            }
        }
    }

    /**
     * 中序遍历 - 递归
     */
    public static <T> void inorderTraversal(Tree.Node<T> root) {
        // 递归的结束条件。
        if (null == root) {
            return;
        }

        // 遍历左子树。
        inorderTraversal(root.left);
        System.out.print(root.val + "\t");
        // 遍历右子树
        inorderTraversal(root.right);
    }

    /**
     * 中序遍历 - 迭代
     */
    public static <T> void inorderTraversal2(Tree.Node<T> root) {
        // 遍历使用的栈
        Deque<Tree.Node<T>> stack = new LinkedList<>();

        while (!stack.isEmpty() || null != root) {
            // 加入左节点.
            while (null != root) {
                stack.push(root);
                root = root.left;
            }

            // 加入节点
            root = stack.pop();
            System.out.print(root.val + "\t");
            // 遍历右子树
            root = root.right;
        }
    }

    /**
     * 中序遍历 - 迭代
     */
    public static <T> void inorderTraversal2_2(Tree.Node<T> root) {
        if (null == root) {
            return;
        }

        Deque<Tree.Node<T>> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Tree.Node<T> node = stack.pop();
            if (null != node) {
                // 压入右节点。
                if (null != node.right) {
                    stack.push(node.right);
                }

                // 压入当前节点。
                stack.push(node);
                // 压入null值作为分隔符。
                stack.push(null);

                // 压入左节点。
                if (null != node.left) {
                    stack.push(node.left);
                }
            } else {
                // 将节点加入集合。
                System.out.print(stack.pop().val + "\t");
            }
        }
    }

    /**
     * 中序遍历 - Morris
     * <p>
     * 1. 当前节点没有前驱节点(左子节点为空)，直接将当前节点加入答案，并遍历当前节点的右子节点
     * 2. 当前节点有前驱节点(左子节点不为空)，找到当前节点的前驱节点：
     * 2.1 前驱节点的右子节点为空： 将前驱节点的右子节点更新为当前节点，并将当前节点更新为当前节点的左子节点(开始遍历左子树)。
     * 2.2 前驱节点的右子节点为当前节点： 将当前节点加入答案，并将它的右子节点重新设为空(结束遍历左子树)。当前节点更新为当前节点的右子节点(开始遍历右子树)。
     *
     * @param root
     */
    public static <T> void inorderTraversal3(Tree.Node<T> root) {
        if (root == null) {
            return;
        }

        // p1为当前节点，p2为前驱节点
        Tree.Node<T> p1 = root, p2 = null;
        while (p1 != null) {
            p2 = p1.left;
            if (p2 != null) {
                // 两种情况： 找前驱节点、置空前驱节点的右子树
                while (p2.right != null && p2.right != p1) {
                    p2 = p2.right;
                }

                if (p2.right == null) {
                    p2.right = p1;
                    p1 = p1.left;
                } else {
                    System.out.print(p1.val + "\t");
                    p2.right = null;
                    p1 = p1.right;
                }
            } else {
                System.out.print(p1.val + "\t");
                p1 = p1.right;
            }
        }
    }

    /**
     * 后序遍历 - 递归
     */
    public static <T> void postorderTraversal(Tree.Node<T> root) {
        // 递归的结束条件。
        if (null == root) {
            return;
        }

        // 遍历左子树。
        postorderTraversal(root.left);
        // 遍历右子树
        postorderTraversal(root.right);
        System.out.print(root.val + "\t");
    }

    /**
     * 后序遍历 - 迭代
     */
    public static <T> void postorderTraversal2(Tree.Node<T> root) {
        // 前序遍历使用的栈。
        Deque<Tree.Node<T>> stack = new LinkedList<>();

        Tree.Node<T> prev = null;
        while (!stack.isEmpty() || null != root) {
            // 加入左节点.
            while (null != root) {
                stack.push(root);
                root = root.left;
            }

            root = stack.peek();
            if (null != root) {
                // 当前已经遍历完了左子树。
                // 压入一个null作为标记。
                stack.push(null);
                // 不为空。
                root = root.right;
            } else {
                // 为空，代表当前节点右子树已经遍历完成。
                stack.pop();
                System.out.print(stack.pop().val + "\t");
                root = null;
            }
        }
    }

    /**
     * 后序遍历 - 迭代
     */
    public static <T> void postorderTraversal2_2(Tree.Node<T> root) {
        if (null == root) {
            return;
        }

        Deque<Tree.Node<T>> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Tree.Node<T> node = stack.pop();
            if (null != node) {
                // 压入根节点。
                stack.push(node);
                // 压入null作为当前节点已经访问过了。
                stack.push(null);

                // 压入右节点。
                if (null != node.right) {
                    stack.push(node.right);
                }
                // 压入左节点。
                if (null != node.left) {
                    stack.push(node.left);
                }
            } else {
                // 如果为空，说明当前节点已经遍历完成。
                System.out.print(stack.pop().val + "\t");
            }
        }
    }

    /**
     * 后序遍历 - Morris
     * <p>
     * 1. 当前节点没有前驱节点(左子节点为空)，则遍历当前节点的右子节点
     * 2. 当前节点有前驱节点(左子节点不为空)，找到当前节点的前驱节点：
     * 2.1 前驱节点的右子节点为空： 将前驱节点的右子节点更新为当前节点，并将当前节点更新为当前节点的左子节点(开始遍历左子树)。
     * 2.2 前驱节点的右子节点为当前节点： 将它的右子节点重新设为空(结束遍历左子树)。倒序输出从当前节点的左子节点到该前驱节点这条路径上的所有节点。当前节点更新为当前节点的右子节点(开始遍历右子树)。
     *
     * @param root
     */
    public static <T> void postorderTraversal3(Tree.Node<T> root) {
        if (root == null) {
            return;
        }

        // p1为当前节点，p2为前驱节点
        Tree.Node<T> p1 = root, p2 = null;
        while (p1 != null) {
            p2 = p1.left;
            if (p2 != null) {
                while (p2.right != null && p2.right != p1) {
                    p2 = p2.right;
                }
                if (p2.right == null) {
                    p2.right = p1;
                    p1 = p1.left;
                    continue;
                } else {
                    p2.right = null;
                    visitReverse(p1.left);
                }
            }
            p1 = p1.right;
        }
        visitReverse(root);
        return;
    }

    /**
     * 首先进行翻转，之后进行顺序访问，最后恢复结构
     *
     * @param node
     */
    private static <T> void visitReverse(Tree.Node<T> node) {
        node = reverse(node);
        while (node != null) {
            System.out.print(node.val + "\t");
            node = node.right;
        }
        reverse(node);
    }

    /**
     * 实现链表翻转
     *
     * @param node
     * @return
     */
    private static <T> Tree.Node<T> reverse(Tree.Node<T> node) {
        Tree.Node<T> newNode = null;
        while (node != null) {
            Tree.Node<T> n = node;
            node = node.right;
            n.right = newNode;
            newNode = n;
        }

        return newNode;
    }

    public static void main(String[] args) {
        Tree tree = Tree.newTree(15);

        System.out.println("前序遍历");
        System.out.print("递  归: ");
        preorderTraversal(tree.getRoot());
        System.out.println();
        System.out.print("迭  代: ");
        preorderTraversal2(tree.getRoot());
        System.out.println();
        System.out.print("迭 代2: ");
        preorderTraversal2_2(tree.getRoot());
        System.out.println();
        System.out.print("Morris: ");
        preorderTraversal3(tree.getRoot());
        System.out.println();

        System.out.println("中序遍历");
        System.out.print("递  归: ");
        inorderTraversal(tree.getRoot());
        System.out.println();
        System.out.print("迭  代: ");
        inorderTraversal2(tree.getRoot());
        System.out.println();
        System.out.print("迭 代2: ");
        inorderTraversal2_2(tree.getRoot());
        System.out.println();
        System.out.print("Morris: ");
        inorderTraversal3(tree.getRoot());
        System.out.println();

        System.out.println("后序遍历");
        System.out.print("递  归: ");
        postorderTraversal(tree.getRoot());
        System.out.println();
        System.out.print("迭  代: ");
        postorderTraversal2(tree.getRoot());
        System.out.println();
        System.out.print("迭 代2: ");
        postorderTraversal2_2(tree.getRoot());
        System.out.println();
        System.out.print("Morris: ");
        postorderTraversal3(tree.getRoot());
        System.out.println();
    }

}
